Usenet 1993 July/InfoMagic USENET CD-ROM July 1993.ISO/sources/unix/volume22/pathalias10/part01

Internet Message Format | 1990-06-07 | 51.6 KB

Subject:  v22i109:  Pathalias, version 10, Part01/03
Newsgroups: comp.sources.unix
Approved: [e-mail]
X-Checksum-Snefru: ed2e8fbf 9221e8c1 b0d37b5e 0970e124

Submitted-by: peter honeyman <[e-mail]>
Posting-number: Volume 22, Issue 109
Archive-name: pathalias10/part01

[ I FTP'd this from peter's machine and am posting it because the version9
  hiccups on the maps.  After this, I'm off to Usenix and a couple of days
  of vacation.  See you in Anaheim, or electronically in a week and a half.
  --r$  ]

Pathalias reads the map data after it has been unpacked from comp.mail.maps,
and generates the "lowest-cost" routes from one host to all other hosts in
the maps.

#! /bin/sh
# This is a shell archive.  Remove anything before this line, then feed it
# into a shell via "sh file" or similar.  To overwrite existing files,
# type "sh file -c".
# The tool that generated this appeared in the comp.sources.unix newsgroup;
# send mail to [e-mail] if you want that tool.
# Contents:  README arpatxt.c mapit.c mem.c pathalias.8
# Wrapped by [e-mail] on Fri Jun  8 09:25:19 1990
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
echo If this archive is complete, you will see the following message:
echo '          "shar: End of archive 1 (of 3)."'
if test -f 'README' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'README'\"
else
  echo shar: Extracting \"'README'\" \(1156 characters\)
  sed "s/^X//" >'README' <<'END_OF_FILE'
XFrom citi!honey Sun Oct  4 23:30 EDT 1987
XDate: 04 Oct 1987 23:30 EDT
XFrom: [e-mail]
XTo: whom it may concern
XSubject: pathalias compilation instructions
X
Xedit config.h
Xmake
X
Xif getopt is undefined, obtain a copy from usenet group
Xcomp.sources.unix and adjust Makefile.
X
Xpathalias input is regularly published in usenet group comp.mail.maps.
X
X    peter
X
Xps:  pathalias, written by steve bellovin and peter honeyman, is in the
X     public domain, and may be used by any person or organization, in
X     any way and for any purpose.
X
Xpps:  There is no warranty of merchantability nor any warranty of fit-
X      ness for a particular purpose nor any other warranty, either ex-
X      press or implied, as to the accuracy of the enclosed materials or
X      as to their suitability for any particular purpose.  Accordingly,
X      the authors assume no responsibility for their use by the recipi-
X      ent.   Further, the authors assume no obligation to furnish any
X      assistance of any kind whatsoever, or to furnish any additional
X      information or documentation.  This paragraph was copied without
X      permission from an old crypt(1) man page.
END_OF_FILE
  if test 1156 -ne `wc -c <'README'`; then
    echo shar: \"'README'\" unpacked with wrong size!
  fi
  # end of 'README'
fi
if test -f 'arpatxt.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'arpatxt.c'\"
else
  echo shar: Extracting \"'arpatxt.c'\" \(13330 characters\)
  sed "s/^X//" >'arpatxt.c' <<'END_OF_FILE'
X#ifndef lint
Xstatic char *sccsid = "@(#)arpatxt.c    9.4 88/09/21";
X#endif
X
X/*
X * convert hosts.txt into pathalias format.
X *
X * alias rule: "host.dom.ain,nickname.arpa,..." -> host = nickname, ...
X */
X
X/* remove the next line for standard or research unix */
X#define BSD
X
X#ifdef BSD
X#define strchr index
X#endif /* BSD */
X
X#include <stdio.h>
X#include <ctype.h>
X
X/* imports */
Xextern char *re_comp(), *malloc(), *strchr(), *calloc();
Xextern char *gets(), *strcpy(), *fgets();
Xextern FILE *fopen();
X
Xtypedef struct node node;
X
Xstruct node {
X    node *child;    /* subdomain or member host */
X    node *parent;    /* parent domain */
X    node *next;    /* sibling in domain tree or host list */
X    char *name;    /* host name */
X    node *alias;    /* list of aliases */
X    node *bucket;
X    node *gateway;
X    int  flag;
X};
X
Xnode *Top;
Xint Atflag, Fflag, Iflag, Vflag;
Xchar *DotArpa = ".ARPA";
Xchar Fname[256], *Fstart;
X
Xnode *newnode(), *find();
Xchar *strsave(), *lowercase();
Xvoid crcinit();
Xlong fold();
XFILE *mkfile();
Xint insert();
X
X#define ISADOMAIN(n) ((n) && *((n)->name) == '.')
X
X/* for node.flag */
X#define COLLISION 1
X
X/* for formatprint() */
X#define PRIVATE        0
X#define HOSTS        1
X#define SUBDOMAINS    2
X
X/* for usage() */
X#define USAGE "usage: %s [-i@] [-g gateway] [-p privatefile] [-f | -d directory] [file ...]\n"
X
Xmain(argc, argv)
X    char **argv;
X{    int c;
X    char *progname;
X    extern char *optarg;
X    extern int optind;
X
X    if ((progname = strchr(argv[0], '/')) != 0)
X        progname++;
X    else
X        progname = argv[0];
X    crcinit();
X
X    Top = newnode();    /* needed for adding gateways */
X    while ((c = getopt(argc, argv, "d:fg:ip:v@")) != EOF)
X        switch(c) {
X        case 'd':
X            strcpy(Fname, optarg);
X            break;
X        case 'f':    /* filter mode -- write on stdout */
X            Fflag++;
X            break;
X        case 'g':
X            gateway(optarg);
X            break;
X        case 'i':
X            Iflag++;
X            break;
X        case 'p':
X            readprivates(optarg);
X            break;
X        case 'v':
X            Vflag++;
X            break;
X        case '@':
X            Atflag++;
X            break;
X        default:
X            usage(progname);
X        }
X
X    if (Fflag && *Fname)
X        usage(progname);
X    if (Iflag)
X        (void) lowercase(DotArpa);
X    if (Top->gateway == 0)
X        fprintf(stderr, "%s: warning: no gateway to top level domains\n", progname);
X
X    Fstart = Fname + strlen(Fname);
X    if (Fstart != Fname) {
X        *Fstart++ = '/';
X        *Fstart = 0;
X    }
X    /* should do the mkdir here instead of the shell script ...*/
X
X    Top->name = "internet";
X    if (optind == argc)
X        scan();
X    else for ( ; optind < argc; optind++) {
X        if (freopen(argv[optind], "r", stdin) == 0) {
X            perror(argv[optind]);
X            continue;
X        }
X        scan();
X    }
X    setuniqflag(Top);    /* look for and mark collisions */
X    hashanalyze();        /* check hash algorithm performance */
X    merge();        /* make unique domain names */
X    dump(Top);        /* print */
X    return 0;
X}
X
Xscan()
X{    static first;
X    char buf0[BUFSIZ], buf1[BUFSIZ], buf2[BUFSIZ];
X
X    if (first++ == 0)
X        (void) re_comp("^HOST.*SMTP");
X    while (gets(buf0) != 0) {
X        if (re_exec(buf0) == 0)
X            continue;
X        if (sscanf(buf0, "HOST : %[^:] : %[^: ]", buf1, buf2) != 2)
X            continue;
X        if (Iflag)
X            (void) lowercase(buf2);
X        if (insert(buf2) != 0)
X            fprintf(stderr, "input error: %s\n", buf0);
X    }
X}
X/*
X * format of private file:
X *    one per line, optionally followed by white space and comments
X *    line starting with # is comment
X */
Xreadprivates(pfile)
X    char *pfile;
X{    FILE *f;
X    node *n;
X    char buf[BUFSIZ], *bptr;
X
X    if ((f = fopen(pfile, "r")) == 0) {
X        perror(pfile);
X        return;
X    }
X    while (fgets(buf, BUFSIZ, f) != 0) {
X        if (*buf == '#')
X            continue;
X        if ((bptr = strchr(buf, ' ')) != 0)
X            *bptr = 0;
X        if ((bptr = strchr(buf, '\t')) != 0)
X            *bptr = 0;
X        if (*buf == 0)
X            continue;
X        n = newnode();
X        n->name = strsave(buf);
X        hash(n);
X    }
X    (void) fclose(f);
X}
Xusage(progname)
X    char *progname;
X{
X    fprintf(stderr, USAGE, progname);
X    exit(1);
X}
X
Xdumpgateways(ndom, f)
X    node *ndom;
X    FILE *f;
X{    node *n;
X
X    for (n = ndom->gateway; n; n = n->next) {
X        fprintf(f, "%s ", n->name);
X        if (Atflag)
X            putc('@', f);
X        fprintf(f, "%s(%s)\t# gateway\n", ndom->name,
X                ndom == Top ? "DEDICATED" : "LOCAL");
X    }
X}
X
Xgateway(buf)
X    char *buf;
X{    node *n, *dom;
X    char *dot;
X
X    dot = strchr(buf, '.');
X    if (dot) {
X        dom = find(dot);
X        *dot = 0;
X    } else
X        dom = Top;
X
X    n = newnode();
X    n->name = strsave(buf);
X    n->next = dom->gateway;
X    dom->gateway = n;
X}
X
Xint
Xinsert(buf)
X    char *buf;
X{    char host[BUFSIZ], *hptr, *dot;
X    node *n;
X
X    for (hptr = host; *hptr = *buf++; hptr++)
X        if (*hptr == ',')
X            break;
X
X    if (*hptr == ',')
X        *hptr = 0;
X    else
X        buf = 0;    /* no aliases */
X
X    if ((dot = strchr(host, '.')) == 0)
X        return 1;    /* can't happen */
X
X    if (strcmp(dot, DotArpa) == 0)
X        buf = 0;        /* no aliases */
X
X    n = find(dot);
X    *dot = 0;
X
X    addchild(n, host, buf);
X    return 0;
X}
X
Xnode *
Xfind(domain)
X    char *domain;
X{    char *dot;
X    node *parent, *child;
X
X    if (domain == 0)
X        return Top;
X    if ((dot = strchr(domain+1, '.')) != 0) {
X        parent = find(dot);
X        *dot = 0;
X    } else
X        parent = Top;
X
X    for (child = parent->child; child; child = child->next)
X        if (strcmp(domain, child->name) == 0)
X            break;
X    if (child == 0) {
X        child = newnode();
X        child->next = parent->child;
X        parent->child = child;
X        child->parent = parent;
X        child->name = strsave(domain);
X    }
X    return child;
X}
X
Xnode *
Xnewnode()
X{
X    node *n;
X
X    if ((n = (node *) calloc(1, sizeof(node))) == 0)
X        abort();
X    return n;
X}
X
Xchar *
Xstrsave(buf)
X    char *buf;
X{    char *mstr;
X
X    if ((mstr = malloc(strlen(buf)+1)) == 0)
X        abort();
X    strcpy(mstr, buf);
X    return mstr;
X}
X
Xaddchild(n, host, aliases)
X    node *n;
X    char *host, *aliases;
X{    node *child;
X
X    /* check for dups?  nah! */
X    child = newnode();
X    child->name = strsave(host);
X    child->parent = n;
X    child->next = n->child;
X    makealiases(child, aliases);
X    n->child = child;
X}
X
X/* yer basic tree walk to make output */
Xdump(n)
X    node *n;
X{    node *child;
X    FILE *f;
X    int privates;
X
X    /* sanity check */
X    if (n != Top && ! ISADOMAIN(n))
X        abort();
X
X    f = mkfile(n);        /* prepare the output file */
X    privates = domprint(n, f);        /* print this domain */
X    dumpgateways(n, f);    /* print any gateways to this domain */
X    if (privates || n == Top)
X        fputs("private {}\n", f);    /* end scope of privates */
X    if (Fflag)
X        putc('\n', f);
X    else
X        (void) fclose(f);
X    for (child = n->child; child; child = child->next)
X        if (child->child)
X            dump(child);
X}
X
Xqcmp(a, b)
X    node **a, **b;
X{
X    return strcmp((*a)->name, (*b)->name);
X}
X
Xdomprint(n, f)
X    node *n;
X    FILE *f;
X{    node *table[8191], *child, *alias;
X    char *cost = 0;
X    int nelem, i, privates = 0;
X
X    /*
X     * dump private definitions.
X     * sort hosts and aliases for pretty output.
X     */
X    if (n != Top) {
X        i = 0;
X        for (child = n->child; child; child = child->next) {
X            table[i++] = child;
X            for (alias = child->alias; alias; alias = alias->next)
X                table[i++] = alias;
X        }
X
X        qsort((char *) table, i, sizeof(table[0]), qcmp);
X        privates = formatprint(f, table, i, PRIVATE, "private", cost);
X    }
X
X    /* dump domains and aliases, sorted for pretty output */
X    i = 0;
X    for (child = n->child; child; child = child->next)
X        table[i++] = child;
X    qsort((char *) table, i, sizeof(table[0]), qcmp);
X
X    /* cost is DEDICATED for hosts in top-level domains, LOCAL o.w. */
X    if (n->parent == Top && strchr(n->name + 1, '.') == 0)
X        cost = "DEDICATED";
X    else
X        cost = "LOCAL";
X
X    (void) formatprint(f, table, i, HOSTS, n->name, cost);
X    (void) formatprint(f, table, i, SUBDOMAINS, n->name, "0");
X
X    /* dump aliases */
X    nelem = i;
X    for (i = 0; i < nelem; i++) {
X        if ((alias = table[i]->alias) == 0)
X            continue;
X        fprintf(f, "%s = %s", table[i]->name, alias->name);
X        for (alias = alias->next; alias; alias = alias->next)
X            fprintf(f, ", %s", alias->name);
X        putc('\n', f);
X    }
X    return privates;
X}
X
Xint
Xformatprint(f, table, nelem, type, lhs, cost)
X    FILE *f;
X    node **table;
X    char *lhs, *cost;
X{    int i, didprint;
X    char buf[128], *bptr;
X
X    sprintf(buf, "%s%s{" /*}*/, lhs, type == PRIVATE ? " " : " = ");
X    bptr = buf + strlen(buf);
X
X    didprint = 0;
X    for (i = 0; i < nelem; i++) {
X        if (type == PRIVATE && ! (table[i]->flag & COLLISION))
X            continue;
X        else if (type == HOSTS && ISADOMAIN(table[i]) )
X            continue;
X        else if (type == SUBDOMAINS && ! ISADOMAIN(table[i]) )
X            continue;
X
X        if ((bptr - buf) + strlen(table[i]->name) > 69) {
X            *bptr = 0;
X            fprintf(f, "%s\n ", buf);    /* continuation */
X            bptr = buf;
X        }
X        sprintf(bptr, "%s, ", table[i]->name);
X        bptr += strlen(bptr);
X        didprint++;
X    }
X    *bptr = 0;
X
X    if (didprint) {
X        fprintf(f, /*{*/ "%s}", buf);
X        if (type != PRIVATE)
X            fprintf(f, "(%s)", cost);
X        putc('\n', f);
X    }
X    return didprint;
X}
X
XFILE *
Xmkfile(n)
X    node *n;
X{    node *parent;
X    char *bptr;
X    FILE *f;
X
X    /* build up the domain name in Fname[] */
X    bptr = Fstart;
X    if (n == Top)
X        strcpy(bptr, n->name);
X    else {
X        strcpy(bptr, n->name + 1);    /* skip leading dot */
X        bptr = bptr + strlen(bptr);
X        parent = n->parent;
X        while (ISADOMAIN(parent)) {
X            strcpy(bptr, parent->name);
X            bptr += strlen(bptr);
X            parent = parent->parent;
X        }
X        *bptr = 0;
X    }
X
X    /* get a stream descriptor */
X    if (Fflag) {
X        printf("# %s\n", Fstart);
X        f = stdout;
X    } else {
X#ifndef BSD
X        Fstart[14] = 0;
X#endif
X        if ((f = fopen(Fname, "w")) == 0) {
X            perror(Fname);
X            exit(1);
X        }
X    }
X    if (n == Top)
X        fprintf(f, "private {%s}\ndead {%s}\n", Top->name, Top->name);
X    return f;
X}
X
X/* map to lower case in place.  return parameter for convenience */
Xchar *
Xlowercase(buf)
X    char *buf;
X{    char *str;
X
X    for (str = buf ; *str; str++)
X        if (isupper(*str))
X            *str -= 'A' - 'a';
X    return buf;
X}
X
X/* get the interesting aliases, attach to n->alias */
Xmakealiases(n, line)
X    node *n;
X    char *line;
X{    char *next, *dot;
X    node *a;
X
X    if (line == 0 || *line == 0)
X        return;
X
X    for ( ; line; line = next) {
X        next = strchr(line, ',');
X        if (next)
X            *next++ = 0;
X        if ((dot = strchr(line, '.')) == 0)
X            continue;
X        if (strcmp(dot, DotArpa) != 0)
X            continue;
X        *dot = 0;
X
X        if (strcmp(n->name, line) == 0)
X            continue;
X
X        a = newnode();
X        a->name = strsave(line);
X        a->next = n->alias;
X        n->alias = a;
X    }
X}
X
X/* make unique domain names */
Xmerge()
X{    register node *n;
X
X    for (n = Top->child; n; n = n->next)
X        make_children_unique(n);
X}
X
X/*
X * another recursive tree walk, this time to make unique domain
X * components.
X *
X * for domains like cc.umich.edu and cc.berkeley.edu, it's inaccurate
X * to describe cc as a member of umich.edu or berkeley.edu.  (i.e., the
X * lousy scoping rules for privates don't permit a clean syntax.)  so.
X *
X * to prevent confusion, tack on to any such domain name its parent domain
X * and promote it in the tree.  e.g., make cc.umich and cc.berkeley
X * subdomains of edu.
X */
X
Xmake_children_unique(parent)
X    node *parent;
X{    node *prev, *child, *next;
X    char buf[BUFSIZ];
X
X    prev = 0;
X    for (child = parent->child; child; child = next) {
X        next = child->next;
X
X        /* skip hosts */
X        if (!ISADOMAIN(child)) {
X            prev = child;
X            continue;
X        }
X
X        /*
X         * promote non-unique domain, or any domain with a
X         * gateway.  (the latter get promoted all the way to
X         * top-level.)
X         */
X        if ((child->flag & COLLISION) == 0 && child->gateway == 0) {
X            /*
X             * uninteresting domain.  make its children
X             * unique and bump prev.
X             */
X            make_children_unique(child);
X            prev = child;
X            continue;
X        }
X
X        /*
X         * gateway or dup domain name found.  don't bump
X         * prev: this node is moving up the tree.
X         */
X
X        /* qualify child domain name */
X        sprintf(buf, "%s%s", child->name, parent->name);
X        cfree(child->name);
X        child->name = strsave(buf);
X
X        /* unlink child out of sibling chain */
X        if (prev)
X            prev->next = child->next;
X        else
X            parent->child = child->next;
X
X        /* link child in as peer of parent */
X        child->next = parent->next;
X        parent->next = child;
X        child->parent = parent->parent;
X
X        /*
X         * reset collision flag; may promote again on
X         * return to caller.
X         */
X        child->flag &= ~COLLISION;
X        hash(child);
X    }
X}
X
X/* another recursive tree walk, this time to set the COLLISION bit. */
Xsetuniqflag(n)
X    node *n;
X{    node *child, *alias;
X
X    /* mark this node in the hash table */
X    hash(n);
X    /* mark the aliases of this node */
X    for (alias = n->alias; alias; alias = alias->next)
X        hash(alias);
X    /* recursively mark this node's children */
X    for (child = n->child; child; child = child->next)
X        setuniqflag(child);
X}
X
X#define NHASH 8191        /* must be prime */
Xnode *Htable[NHASH];        /* hash table */
X
Xhash(n)
X    node *n;
X{    node **bucket, *b;
X
X    bucket = Htable + (fold(n->name) % NHASH);
X    for (b = *bucket; b; b = b->bucket)
X        if (strcmp(n->name, b->name) == 0) {
X            b->flag |= COLLISION;
X            n->flag |= COLLISION;
X            return;
X        }
X
X    n->bucket = *bucket;
X    *bucket = n;
X}
X
X/* stolen from pathalias:addnode.c, q.v. */
X#define POLY    0x48000000        /* 31-bit polynomial */
Xlong CrcTable[128];
X
Xvoid
Xcrcinit()
X{    register int i,j;
X    register long sum;
X
X    for (i = 0; i < 128; i++) {
X        sum = 0;
X        for (j = 7-1; j >= 0; --j)
X            if (i & (1 << j))
X                sum ^= POLY >> j;
X        CrcTable[i] = sum;
X    }
X}
X
Xlong
Xfold(s)
X    register char *s;
X{    register long sum = 0;
X    register int c;
X
X    while (c = *s++)
X        sum = (sum >> 7) ^ CrcTable[(sum ^ c) & 0x7f];
X    return sum;
X}
X
Xhashanalyze()
X{    int nodecount = 0, maxlen = 0, len, i, probes = 0;
X    node *n;
X
X    if (!Vflag)
X        return;
X
X    for (i = 0; i < NHASH; i++) {
X        len = 0;
X        for (n = Htable[i]; n; n = n->bucket) {
X            len++;
X            probes += len;
X        }
X        nodecount += len;
X        if (len > maxlen)
X            maxlen = len;
X    }
X    fprintf(stderr,
X      "load = %2.2f, probes/access = %2.2f, %d nodes, max chain is %d\n",
X      (double) nodecount / (double) NHASH,
X      (double) probes / (double) nodecount, nodecount, maxlen);
X}
END_OF_FILE
  if test 13330 -ne `wc -c <'arpatxt.c'`; then
    echo shar: \"'arpatxt.c'\" unpacked with wrong size!
  fi
  # end of 'arpatxt.c'
fi
if test -f 'mapit.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'mapit.c'\"
else
  echo shar: Extracting \"'mapit.c'\" \(15685 characters\)
  sed "s/^X//" >'mapit.c' <<'END_OF_FILE'
X/* pathalias -- by steve bellovin, as told to peter honeyman */
X#ifndef lint
Xstatic char    *sccsid = "@(#)mapit.c    9.13 88/06/12";
X#endif
X
X#include "def.h"
X
X#define chkheap(i)    /* void */
X#define chkgap()    /* int */
X
X#define trprint(stream, n) \
X    fprintf((stream), (n)->n_flag & NTERMINAL ? "<%s>" : "%s", (n)->n_name)
X
X/* exports */
X/* invariant while mapping: Nheap < Hashpart */
Xlong Hashpart;        /* start of unreached nodes */
Xlong Nheap;        /* end of heap */
Xlong NumNcopy, Nlink, NumLcopy;
X
Xvoid mapit();
X
X/* imports */
Xextern long Nheap, Hashpart, Tabsize, Tcount;
Xextern int Tflag, Vflag;
Xextern node **Table, *Home;
Xextern char *Linkout, *Graphout;
X
Xextern void freelink(), resetnodes(), printit(), dumpgraph();
Xextern void showlinks(), die();
Xextern long pack(), allocation();
Xextern link *newlink(), *addlink();
Xextern int maptrace(), tiebreaker();
Xextern node *ncopy();
X
X
X/* privates */
Xstatic long    Heaphighwater;
Xstatic link    **Heap;
X
XSTATIC void insert(), heapup(), heapdown(), heapswap(), backlinks();
XSTATIC void setheapbits(), mtracereport(), heapchildren(), otracereport();
XSTATIC link *min_node();
XSTATIC int dehash(), skiplink(), skipterminalalias();
XSTATIC Cost costof();
XSTATIC node *mappedcopy();
X
X/* transform the graph to a shortest-path tree by marking tree edges */
Xvoid
Xmapit()
X{    register node *n;
X    register link *l;
X
X    vprintf(stderr, "*** mapping\ttcount = %ld\n", Tcount);
X    Tflag = Tflag && Vflag;        /* tracing here only if verbose */
X    /* re-use the hash table space for the heap */
X    Heap = (link **) Table;
X    Hashpart = pack(0L, Tabsize - 1);
X
X    /* expunge penalties from -a option and make circular copy lists */
X    resetnodes();
X
X    if (Linkout && *Linkout)    /* dump cheapest links */
X        showlinks();
X    if (Graphout && *Graphout)    /* dump the edge list */
X        dumpgraph();
X
X    /* insert Home to get things started */
X    l = newlink();        /* link to get things started */
X    l->l_to = Home;
X    (void) dehash(Home);
X    insert(l);
X
X    /* main mapping loop */
X    do {
X        Heaphighwater = Nheap;
X        while ((l = min_node()) != 0) {
X            l->l_flag |= LTREE;
X            n = l->l_to;
X            if (n->n_flag & MAPPED)        /* sanity check */
X                die("mapped node in heap");
X            if (Tflag && maptrace(n, n))
X                otracereport(n);    /* tracing */
X            chkheap(1); chkgap();        /* debugging */
X            n->n_flag |= MAPPED;
X            heapchildren(n);    /* add children to heap */
X        }
X        vprintf(stderr, "heap hiwat %d\nalloc %ldk, ncopy = %ld, nlink = %ld, lcopy = %ld\n", Heaphighwater, allocation(), NumNcopy, Nlink, NumLcopy);
X
X        if (Nheap != 0)        /* sanity check */
X            die("null entry in heap");
X
X        /*
X         * add back links from unreachable hosts to reachable
X         * neighbors, then remap.  asymptotically, this is
X         * quadratic; in practice, this is done once or twice,
X         * when n is small.
X         */
X        backlinks();
X    } while (Nheap > 0);
X
X    if (Hashpart < Tabsize) {
X        int foundone = 0;
X
X        for ( ; Hashpart < Tabsize; Hashpart++) {
X            if (Table[Hashpart]->n_flag & ISPRIVATE)
X                continue;
X            if (foundone++ == 0)
X                fputs("You can't get there from here:\n", stderr);
X            putc('\t', stderr);
X            trprint(stderr, Table[Hashpart]);
X            putc('\n', stderr);
X        }
X    }
X}
X
XSTATIC void
Xheapchildren(n)
X    register node *n;
X{    register link *l;
X    register node *next;
X    register int mtrace;
X    register Cost cost;
X
X    for (l = n->n_link; l; l = l->l_next) {
X
X        next = l->l_to;        /* neighboring node */
X        mtrace = Tflag && maptrace(n, next);
X
X        if (l->l_flag & LTREE)
X            continue;
X
X        if (l->l_flag & LTERMINAL)
X            l->l_to = next = ncopy(n, l);
X
X        if ((n->n_flag & NTERMINAL) && (l->l_flag & LALIAS))
X            if (skipterminalalias(n, next))
X                continue;
X            else
X                l->l_to = next = ncopy(n, l);
X
X        if (next->n_flag & MAPPED) {
X            if (mtrace)
X                mtracereport(n, l, "-\talready mapped");
X            continue;
X        }
X        cost = costof(n, l);
X
X        if (skiplink(l, n, cost, mtrace))
X            continue;
X
X        /*
X         * put this link in the heap and restore the
X         * heap property.
X         */
X        if (mtrace) {
X            if (next->n_parent)
X                mtracereport(next->n_parent, l, "*\tdrop");
X            mtracereport(n, l, "+\tadd");
X        }
X        next->n_parent = n;
X        if (dehash(next) == 0) {  /* first time */
X            next->n_cost = cost;
X            insert(l);      /* insert at end */
X            heapup(l);
X        } else {
X            /* replace inferior path */
X            Heap[next->n_tloc] = l;
X            if (cost > next->n_cost) {
X                /* increase cost (gateway) */
X                next->n_cost = cost;
X                heapdown(l);
X            } else if (cost < next->n_cost) {
X                /* cheaper route */
X                next->n_cost = cost;
X
X                heapup(l);
X            }
X        }
X        setheapbits(l);
X        chkheap(1);
X
X    }
X}
X
X/*
X * bizarro special case.  this merits comment.
X *
X * n is a terminal node just sucked out of the heap, next is an alias
X * for n.  because n is terminal, it must have one or more "copies."
X * if next is one of those copies, don't put next in the heap.
X *
X * does that clear things up?
X */
XSTATIC int
Xskipterminalalias(n, next)
X    node *n, *next;
X{
X
X    while (n->n_flag & NALIAS) {
X        n = n->n_parent;
X        if (ALTEREGO(n, next))
X            return 1;
X    }
X    return 0;
X}
X
X/*
X * return 1 if we definitely don't want want this link in the
X * shortest path tree, 0 if we might want it, i.e., best so far.
X *
X * if tracing is turned on, report only if this node is being skipped.
X */
XSTATIC int
Xskiplink(l, parent, cost, trace)
X    link *l;        /* new link to this node */
X    node *parent;        /* (potential) new parent of this node */
X    register Cost cost;    /* new cost to this node */
X    int trace;        /* trace this link? */
X{    register node *n;    /* this node */
X    register link *lheap;        /* old link to this node */
X
X    n = l->l_to;
X
X    /* first time we've reached this node? */
X    if (n->n_tloc >= Hashpart)
X        return 0;
X
X    lheap = Heap[n->n_tloc];
X
X    /* examine links to nets that require gateways */
X    if (GATEWAYED(n)) {
X        /* if exactly one is a gateway, use it */
X        if ((lheap->l_flag & LGATEWAY) && !(l->l_flag & LGATEWAY)) {
X            if (trace)
X                mtracereport(parent, l, "-\told gateway");
X            return 1;    /* old is gateway */
X        }
X        if (!(lheap->l_flag & LGATEWAY) && (l->l_flag & LGATEWAY))
X            return 0;    /* new is gateway */
X
X        /* no gateway or both gateways;  resolve in standard way ... */
X    }
X
X    /* examine dup link (sanity check) */
X    if (n->n_parent == parent && (DEADLINK(lheap) || DEADLINK(l)))
X        die("dup dead link");
X
X    /*  examine cost */
X    if (cost < n->n_cost)
X        return 0;
X    if (cost > n->n_cost) {
X        if (trace)
X            mtracereport(parent, l, "-\tcheaper");
X        return 1;
X    }
X
X    /* all other things being equal, ask the oracle */
X    if (tiebreaker(n, parent)) {
X        if (trace)
X            mtracereport(parent, l, "-\ttiebreaker");
X        return 1;
X    }
X    return 0;
X}
X
X/* compute cost to l->l_to via parent */
XSTATIC Cost
Xcostof(prev, l)
X    register node *prev;
X    register link *l;
X{    register node *next;
X    register Cost cost;
X
X    if (l->l_flag & LALIAS)
X        return prev->n_cost;    /* by definition */
X
X    next = l->l_to;
X    cost = prev->n_cost + l->l_cost;    /* basic cost */
X
X    /*
X     * heuristics:
X     *    charge for a dead link.
X     *    charge for getting past a terminal host
X     *        or getting out of a dead host.
X     *    charge for getting into a gatewayed net (except at a gateway).
X     *    discourage mixing of syntax (when prev is a host).
X     *
X     * life was simpler when pathalias computed true shortest paths.
X     */
X    if (DEADLINK(l))
X        cost += INF;                /* dead link */
X    if (DEADHOST(prev))
X        cost += INF;                /* dead parent */
X    if (GATEWAYED(next) && !(l->l_flag & LGATEWAY))
X        cost += INF;                /* not gateway */
X    if (!ISANET(prev)) {
X        if ((NETDIR(l) == LLEFT && (prev->n_flag & HASRIGHT))
X         || (NETDIR(l) == LRIGHT && (prev->n_flag & HASLEFT)))
X            cost += INF;            /* mixed syntax */
X    }
X
X    return cost;
X}
X
X/* binary heap implementation of priority queue */
X
XSTATIC void
Xinsert(l)
X    link *l;
X{    register node *n;
X
X    n = l->l_to;
X    if (n->n_flag & MAPPED)
X        die("insert mapped node");
X
X    Heap[n->n_tloc] = 0;
X    if (Heap[Nheap+1] != 0)
X        die("heap error in insert");
X    if (Nheap++ == 0) {
X        Heap[1] = l;
X        n->n_tloc = 1;
X        return;
X    }
X    if (Vflag && Nheap > Heaphighwater)
X        Heaphighwater = Nheap;    /* diagnostics */
X
X    /* insert at the end.  caller must heapup(l). */
X    Heap[Nheap] = l;
X    n->n_tloc = Nheap;
X}
X
X/*
X * "percolate" up the heap by exchanging with the parent.  as in
X * min_node(), give tiebreaker() a chance to produce better, stable
X * routes by moving nets and domains close to the root, nets closer
X * than domains.
X *
X * i know this seems obscure, but it's harmless and cheap.  trust me.
X */
XSTATIC void
Xheapup(l)
X    link *l;
X{    register long cindx, pindx;    /* child, parent indices */
X    register Cost cost;
X    register node *child, *parent;
X
X    child = l->l_to;
X
X    cost = child->n_cost;
X    for (cindx = child->n_tloc; cindx > 1; cindx = pindx) {
X        pindx = cindx / 2;
X        if (Heap[pindx] == 0)    /* sanity check */
X            die("impossible error in heapup");
X        parent = Heap[pindx]->l_to;
X        if (cost > parent->n_cost)
X            return;
X
X        /* net/domain heuristic */
X        if (cost == parent->n_cost) {
X            if (!ISANET(child))
X                return;
X            if (!ISADOMAIN(parent))
X                return;
X            if (ISADOMAIN(child))
X                return;
X        }
X        heapswap(cindx, pindx);
X    }
X}
X
X/* extract min (== Heap[1]) from heap */
XSTATIC link    *
Xmin_node()
X{    link *rval, *lastlink;
X    register link **rheap;
X
X    if (Nheap == 0)
X        return 0;
X
X    rheap = Heap;        /* in register -- heavily used */
X    rval = rheap[1];    /* return this one */
X
X    /* move last entry into root and reheap */
X    lastlink = rheap[Nheap];
X    rheap[Nheap] = 0;
X
X    if (--Nheap) {
X        rheap[1] = lastlink;
X        lastlink->l_to->n_tloc = 1;
X        heapdown(lastlink);    /* restore heap property */
X    }
X
X    return rval;
X}
X
X/*
X * swap Heap[i] with smaller child, iteratively down the tree.
X *
X * given the opportunity, attempt to place nets and domains
X * near the root.  this helps tiebreaker() shun domain routes.
X */
X
XSTATIC void
Xheapdown(l)
X    link *l;
X{    register long pindx, cindx;
X    register link **rheap = Heap;    /* in register -- heavily used */
X    node *child, *rchild, *parent;
X
X    pindx = l->l_to->n_tloc;
X    parent = rheap[pindx]->l_to;    /* invariant */
X    for ( ; (cindx = pindx * 2) <= Nheap; pindx = cindx) {
X        /* pick lhs or rhs child */
X        child = rheap[cindx]->l_to;
X        if (cindx < Nheap) {
X            /* compare with rhs child */
X            rchild = rheap[cindx+1]->l_to;
X            /*
X             * use rhs child if smaller than lhs child.
X             * if equal, use rhs if net or domain.
X             */
X            if (child->n_cost > rchild->n_cost) {
X                child = rchild;
X                cindx++;
X            } else if (child->n_cost == rchild->n_cost)
X                if (ISANET(rchild)) {
X                    child = rchild;
X                    cindx++;
X                }
X        }
X
X        /* child is the candidate for swapping */
X        if (parent->n_cost < child->n_cost)
X            break;
X
X        /*
X         * heuristics:
X         *    move nets/domains up
X         *    move nets above domains
X         */
X        if (parent->n_cost == child->n_cost) {
X            if (!ISANET(child))
X                break;
X            if (ISANET(parent) && ISADOMAIN(child))
X                break;
X        }
X
X        heapswap(pindx, cindx);
X    }
X}
X
X/* exchange Heap[i] and Heap[j] pointers */
XSTATIC void
Xheapswap(i, j)
X    long i, j;
X{    register link *temp, **rheap;
X
X    rheap = Heap;    /* heavily used -- put in register */
X    temp = rheap[i];
X    rheap[i] = rheap[j];
X    rheap[j] = temp;
X    rheap[j]->l_to->n_tloc = j;
X    rheap[i]->l_to->n_tloc = i;
X}
X
X/* return 1 if n is already de-hashed (n_tloc < Hashpart), 0 o.w. */
XSTATIC int
Xdehash(n)
X    register node *n;
X{
X    if (n->n_tloc < Hashpart)
X        return 1;
X
X    /* swap with entry in Table[Hashpart] */
X    Table[Hashpart]->n_tloc = n->n_tloc;
X    Table[n->n_tloc] = Table[Hashpart];
X    Table[Hashpart] = n;
X
X    n->n_tloc = Hashpart++;
X    return 0;
X}
X
X/*
X * everything reachable has been mapped.  what to do about any
X * unreachable hosts?  the sensible thing to do is to dump them on
X * stderr and be done with it.  unfortunately, there are hundreds of
X * such hosts in the usenet maps.  so we take the low road: for each
X * unreachable host, we add a back link from its cheapest mapped child,
X * in the faint that a reverse path works.
X *
X * beats me why people want their error output in their map databases.
X */
XSTATIC void
Xbacklinks()
X{    register link *l;
X    register node *n, *child;
X    node *nomap;
X    long i;
X
X    /* hosts from Hashpart to Tabsize are unreachable */
X    for (i = Hashpart; i < Tabsize; i++) {
X        nomap = Table[i];
X        /* if a copy has been mapped, we're ok */
X        if (nomap->n_copy != nomap) {
X            dehash(nomap);
X            Table[nomap->n_tloc] = 0;
X            nomap->n_tloc = 0;
X            continue;
X        }
X
X        /* TODO: simplify this */
X        /* add back link from minimal cost child */
X        child = 0;
X        for (l = nomap->n_link; l; l = l->l_next) {
X            n = l->l_to;
X            /* never ever ever crawl out of a domain */
X            if (ISADOMAIN(n))
X                continue;
X            if ((n = mappedcopy(n)) == 0)
X                continue;
X            if (child == 0) {
X                child = n;
X                continue;
X            }
X            if (n->n_cost > child->n_cost)
X                continue;
X            if (n->n_cost == child->n_cost) {
X                nomap->n_parent = child; /* for tiebreaker */
X                if (tiebreaker(nomap, n))
X                    continue;
X            }
X            child = n;
X        }
X        if (child == 0)
X            continue;
X        (void) dehash(nomap);
X        l = addlink(child, nomap, INF, DEFNET, DEFDIR);    /* INF cost */
X        nomap->n_parent = child;
X        nomap->n_cost = costof(child, l);
X        insert(l);
X        heapup(l);
X        if (Vflag > 1)
X            fprintf(stderr, "backlink: %s <- %s\n", nomap->n_name, child->n_name);
X    }
X    vprintf(stderr, "%d backlinks\n", Nheap);
X}
X
X/* find a mapped copy of n if it exists */
XSTATIC node *
Xmappedcopy(n)
X    register node *n;
X{    register node *ncp;
X
X    if (n->n_flag & MAPPED)
X        return n;
X    for (ncp = n->n_copy; ncp != n; ncp = ncp->n_copy)
X        if (ncp->n_flag & MAPPED)
X            return ncp;
X    return 0;
X}
X
X/*
X * l has just been added or changed in the heap,
X * so reset the state bits for l->l_to.
X */
XSTATIC void
Xsetheapbits(l)
X    register link *l;
X{    register node *n;
X    register node *parent;
X
X    n = l->l_to;
X    parent = n->n_parent;
X    n->n_flag &= ~(NALIAS|HASLEFT|HASRIGHT);    /* reset */
X
X    /* record whether link is an alias */
X    if (l->l_flag & LALIAS) {
X        n->n_flag |= NALIAS;
X        /* TERMINALity is inherited by the alias */
X        if (parent->n_flag & NTERMINAL)
X            n->n_flag |= NTERMINAL;
X    }
X
X    /* set left/right bits */
X    if (NETDIR(l) == LLEFT || (parent->n_flag & HASLEFT))
X        n->n_flag |= HASLEFT;
X    if (NETDIR(l) == LRIGHT || (parent->n_flag & HASRIGHT))
X        n->n_flag |= HASRIGHT;
X}
X
XSTATIC void
Xmtracereport(from, l, excuse)
X    node *from;
X    link *l;
X    char *excuse;
X{    node *to = l->l_to;
X
X    fprintf(stderr, "%-16s ", excuse);
X    trprint(stderr, from);
X    fputs(" -> ", stderr);
X    trprint(stderr, to);
X    fprintf(stderr, " (%ld, %ld, %ld) ", from->n_cost, l->l_cost, to->n_cost);
X    if (to->n_parent) {
X        trprint(stderr, to->n_parent);
X        fprintf(stderr, " (%ld)", to->n_parent->n_cost);
X    }
X    putc('\n', stderr);
X}
X
XSTATIC void
Xotracereport(n)
X    node *n;
X{
X    if (n->n_parent)
X        trprint(stderr, n->n_parent);
X    else
X        fputs("[root]", stderr);
X    fputs(" -> ", stderr);
X    trprint(stderr, n);
X    fputs(" mapped\n", stderr);
X}
X
X#if 0
X/* extremely time consuming, exhaustive check of heap sanity. */
Xchkheap(i)
X{    int lhs, rhs;
X
X    lhs = i * 2;
X    rhs = lhs + 1;
X
X    if (lhs <= Nheap) {
X        if (Heap[i]->l_to->n_cost > Heap[lhs]->l_to->n_cost)
X            die("chkheap failure on lhs");
X        chkheap(lhs);
X    }
X    if (rhs <= Nheap) {
X        if (Heap[i]->l_to->n_cost > Heap[rhs]->l_to->n_cost)
X            die("chkheap failure on rhs");
X        chkheap(rhs);
X    }
X#if 00
X    /* this hasn't been used for years */
X    for (i = 1; i < Nheap; i++) {
X        link *l;
X
X        vprintf(stderr, "%5d %-16s", i, Heap[i]->l_to->n_name);
X        if ((l = Heap[i]->l_to->n_link) != 0) do {
X            vprintf(stderr, "%-16s", l->l_to->n_name);
X        } while ((l = l->l_next) != 0);
X        vprintf(stderr, "\n");
X    }
X    for (i = Hashpart; i < Tabsize; i++) {
X        link *l;
X        node *n;
X
X        vprintf(stderr, "%5d %-16s", i, Table[i]->n_name);
X        if ((l = Table[i]->n_link) != 0) do {
X            vprintf(stderr, "%-16s", l->l_to->n_name);
X        } while ((l = l->l_next) != 0);
X        vprintf(stderr, "\n");
X    }
X#endif /*00*/
X
X}
X#endif /*0*/
X
X/* this isn't much use */
X#if 0
XSTATIC int
Xchkgap()
X{    static int gap = -1;
X    int newgap;
X
X    newgap = Hashpart - Nheap;
X    if (gap == -1 || newgap < gap)
X        gap = newgap;
X    return gap;
X}
X#endif /*0*/
END_OF_FILE
  if test 15685 -ne `wc -c <'mapit.c'`; then
    echo shar: \"'mapit.c'\" unpacked with wrong size!
  fi
  # end of 'mapit.c'
fi
if test -f 'mem.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'mem.c'\"
else
  echo shar: Extracting \"'mem.c'\" \(4416 characters\)
  sed "s/^X//" >'mem.c' <<'END_OF_FILE'
X/* pathalias -- by steve bellovin, as told to peter honeyman */
X#ifndef lint
Xstatic char    *sccsid = "@(#)mem.c    9.2 88/06/10";
X#endif
X
X#include "def.h"
X
X/* exports */
Xlong Ncount;
Xextern void freelink(), wasted(), freetable();
Xextern long allocation();
X
X/* imports */
Xextern char *Netchars;
Xextern int Vflag;
Xextern char *sbrk();
Xextern void die();
Xextern int strlen();
X
X/* privates */
XSTATIC void nomem();
Xstatic link *Lcache;
Xstatic unsigned int Memwaste;
X
Xlink    *
Xnewlink()
X{    register link *rval;
X
X    if (Lcache) {
X         rval = Lcache;
X        Lcache = Lcache->l_next;
X        strclear((char *) rval, sizeof(link));
X    } else if ((rval = (link * ) calloc(1, sizeof(link))) == 0)
X        nomem();
X    return rval;
X}
X
X/* caution: this destroys the contents of l_next */
Xvoid
Xfreelink(l)
X    link *l;
X{
X    l->l_next = Lcache;
X    Lcache = l;
X}
X
Xnode    *
Xnewnode()
X{    register node *rval;
X
X    if ((rval = (node * ) calloc(1, sizeof(node))) == 0)
X        nomem();
X    Ncount++;
X    return rval;
X}
X
Xchar    *
Xstrsave(s)
X    char *s;
X{    register char *r;
X
X    if ((r = malloc((unsigned) strlen(s) + 1)) == 0)
X        nomem();
X    (void) strcpy(r, s);
X    return r;
X}
X
X#ifndef strclear
Xvoid
Xstrclear(str, len)
X    register char *str;
X    register long len;
X{
X    while (--len >= 0)
X        *str++ = 0;
X}
X#endif /*strclear*/
X
Xnode    **
Xnewtable(size)
X    long size;
X{    register node **rval;
X
X    if ((rval = (node **) calloc(1, (unsigned int) size * sizeof(node *))) == 0)
X        nomem();
X    return rval;
X}
X
Xvoid
Xfreetable(t, size)
X    node **t;
X    long size;
X{
X#ifdef MYMALLOC
X    extern void addtoheap();
X
X    addtoheap((char *) t, size * sizeof(node *));
X#else
X    free((char *) t);
X#endif
X}
X
XSTATIC void
Xnomem()
X{
X    static char epitaph[128];
X
X    sprintf(epitaph, "out of memory (%ldk allocated)", allocation());
X    die(epitaph);
X}
X
X/* data space allocation -- main sets `dataspace' very early */
Xlong
Xallocation()
X{
X    static char *dataspace;
X    long rval;
X
X    if (dataspace == 0) {        /* first time */
X        dataspace = sbrk(0);    /* &end? */
X        return 0;
X    }
X    rval = (sbrk(0) - dataspace)/1024;
X    if (rval < 0)            /* funny architecture? */
X        rval = -rval;
X    return rval;
X}
X
X/* how much memory has been wasted? */
Xvoid
Xwasted()
X{
X    if (Memwaste == 0)
X        return;
X    vprintf(stderr, "memory allocator wasted %ld bytes\n", Memwaste);
X}
X
X#ifdef MYMALLOC
X
X/* use c library malloc/calloc here, and here only */
X#undef malloc
X#undef calloc
X
X/* imports */
Xextern char *malloc(), *calloc();
X
X/* private */
XSTATIC int align();
X
X/* allocate in MBUFSIZ chunks.  4k works ok (less 16 for malloc quirks). */
X#define MBUFSIZ (4 * 1024 - 16)
X
X/*
X * mess with ALIGN at your peril.  longword (== 0 mod 4)
X * alignment seems to work everywhere.
X */
X
X#define ALIGN 2
X
Xtypedef struct heap heap;
Xstruct heap {
X    heap *h_next;
X    long h_size;
X};
X
Xstatic heap *Mheap;    /* not to be confused with a priority queue */
X
XSTATIC void
Xaddtoheap(p, size)
X    char *p;
X    long size;
X{    int adjustment;
X    heap *pheap;
X
X    /* p is aligned, but it doesn't hurt to check */
X    adjustment = align(p);
X    p += adjustment;
X    size -= adjustment;
X
X    if (size < 1024)
X        return;        /* can't happen */
X    pheap = (heap *) p;    /* pheap is shorthand */
X    pheap->h_next = Mheap;
X    pheap->h_size = size;
X    Mheap = pheap;
X}
X
X/*
X * buffered malloc()
X *    returns space initialized to 0.  calloc isn't used, since
X *    strclear can be faster.
X *
X * free is ignored, except for very large objects,
X * which are returned to the heap with addtoheap().
X */
X
Xchar    *
Xmymalloc(n)
X    register unsigned int n;
X{    static unsigned int size; /* how much do we have on hand? */
X    static char *mstash;      /* where is it? */
X    register char *rval;
X
X    if (n >= 1024) {        /* for hash table */
X        rval = malloc(n);    /* aligned */
X        if (rval)
X            strclear(rval, n);
X        return rval;
X    }
X
X    n += align((char *) n);    /* keep everything aligned */
X
X    if (n > size) {
X        Memwaste += size;    /* toss the fragment */
X        /* look in the heap */
X        if (Mheap) {
X            mstash = (char *) Mheap;    /* aligned */
X            size = Mheap->h_size;
X            Mheap = Mheap->h_next;
X        } else {
X            mstash = malloc(MBUFSIZ);    /* aligned */
X            if (mstash == 0) {
X                size = 0;
X                return 0;
X            }
X            size = MBUFSIZ;
X        }
X        strclear(mstash, size);        /* what if size > 2^16? */
X    }
X    rval = mstash;
X    mstash += n;
X    size -= n;
X    return rval;
X}
X
X/*
X * what's the (mis-)alignment of n?  return the complement of
X * n mod 2^ALIGN
X */
XSTATIC int
Xalign(n)
X    char *n;
X{    register int abits;    /* misalignment bits in n */
X
X    abits = (int) n & ~(0xff << ALIGN) & 0xff;
X    if (abits == 0)
X        return 0;
X    return (1 << ALIGN) - abits;
X}
X
X#endif /*MYMALLOC*/
END_OF_FILE
  if test 4416 -ne `wc -c <'mem.c'`; then
    echo shar: \"'mem.c'\" unpacked with wrong size!
  fi
  # end of 'mem.c'
fi
if test -f 'pathalias.8' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'pathalias.8'\"
else
  echo shar: Extracting \"'pathalias.8'\" \(12597 characters\)
  sed "s/^X//" >'pathalias.8' <<'END_OF_FILE'
X.\" @(#)pathalias.8    9.5 88/05/10
X.TH PATHALIAS 8 "5/10/88" "Public Domain"
X.SH NAME
Xpathalias, makedb, arpatxt \- mail routing tools
X.SH SYNOPSIS
X.B pathalias
X[
X.B \-ivcDf
X] [
X.BI \-t \0link
X] [
X.BI \-l \0host
X] [
X.BI \-d \0link
X] [
X.ig
X.\" for pathparse.
X.BI \-g \0file
X] [
X..
X.I files ...
X]
X.PP
X.B makedb
X[
X.B \-a
X] [
X.BI \-o \0dbmfile
X] [
X.I files ...
X]
X.PP
X.B arpatxt
X[
X.B \-@fi
X] [
X.BI \-g \0gateway
X] [
X.BI \-p \0privatefile
X] [
X.BI \-d \0directory
X] [
X.I files ...
X]
X.ad b
X.SH DESCRIPTION
X.I Pathalias
Xcomputes the shortest paths and corresponding routes from one host
X(computer system) to all other known, reachable hosts.
X.I Pathalias
Xreads host-to-host connectivity
Xinformation on standard input or in the named
X.IR files ,
Xand writes a list of
Xhost-route pairs on the standard output.
X.PP
XHere are the
X.I pathalias
Xoptions:
X.TP 6
X.B \-i
XIgnore case:  map all host names to lower case.
XBy default, case is significant.
X.TP
X.B \-c
XPrint costs: print the path cost before each host-route pair.
X.TP
X.B \-v
XVerbose: report some statistics on the standard error output.
X.TP
X.B \-D
XTerminal domains: see
X.I domains
Xsection.
X.TP
X.B \-f
XFirst hop cost: the printed cost is the cost to the first relay in a path,
Xinstead of the cost of the path itself; implies (and overrides) the
X.B \-c
Xoption.
X.ig
X.\" the -g option is for pathparse and is not for public consumption (yet!).
X.TP
X.BI \-g \0file
XDump the edges of the graph into the named file.
X..
X.TP
X.BI \-l \0host
XSet local host name to
X.IR host .
XBy default,
X.I pathalias
Xdiscovers the local host name in a system-dependent way.
X.TP
X.BI \-d \0arg
XDeclare a dead link, host, or network.
XIf
X.I arg
Xis of the form ``host-1!host-2,'' the link from host-1 to host-2
Xis treated as an extremely high cost (\fIi.e.\fP, \s-1DEAD\s0) link.
XIf
X.I arg
Xis a single host name,
Xthat host is treated as dead
Xand is used as a relay host of last resort on any path.
XIf
X.I arg
Xis a network name, the network requires a gateway.
X.TP
X.BI \-t \0arg
XTrace input for link, host or network on the standard error output.
XThe form of
X.I arg
Xis as above.
X.PP
X.I Makedb
Xtakes
X.I pathalias
Xoutput and creates or appends to a
X.IR dbm (3)
Xdatabase.
X.PP
XHere are the
X.I makedb
Xoptions:
X.TP 6
X.B \-a
XAppend to an existing database;
Xby default,
X.I makedb
Xtruncates the database.
X.TP
X.BI \-o \0dbmfile
XIdentify the output file base name.
X.PP
X.I Arpatxt
Xconverts the Internet hosts table
X.I hosts.txt
Xinto
X.I pathalias
Xinput.
X.PP
XHere are the
X.I arpatxt
Xoptions:
X.TP 6
X.B \-@
XGenerate
X.I pathalias
Xinput that specifies `@' style addressing.  The default
Xis to produce
X.I pathalias
Xinput that specifies `!' style addressing.
X.TP
X.B \-f
X\&``Filter mode'' \(em write output on stdout.  Normally,
X.I arpatxt
Xwrites the description of each domain into a separate file.
X.TP
X.B \-i
XMap output to lower case.
X.TP
X.BI \-g \0arg
XDeclare a gateway to the Internet or one of its subdomains.  If
X.I arg
Xcontains one or more dots, the left-hand side component that contains
Xno dots is declared a gateway to the domain to the right of the dot.
XOtherwise,
X.I arg
Xis declared a gateway to the Internet as a whole.
X.TP
X.BI \-p \0privatefile
X.I Privatefile
Xcontains a list of host names that conflict with other names.
X.TP
X.BI \-d \0directory
XWrite output files in
X.IR directory .
X.SS \fIPathalias\fP Input Format
XA line beginning with white space continues the preceding line.
XAnything following `#' on an input line is ignored.
X.PP
XA list of host-to-host connections consists of a ``from'' host in column 1,
Xfollowed by white space,
Xfollowed by a comma-separated list of ``to' hosts, called
X.IR links .
XA link may be preceded or followed by a network character to use
Xin the route.
XValid network characters are `!' (default), `@', `:', and `%'.
XA link (and network character, if present) may be
Xfollowed by a ``cost'' enclosed in parentheses.
XCosts may be arbitrary
Xarithmetic expressions involving numbers, parentheses, `+', `\-', `*',
Xand `/'.
XNegative costs are prohibited.
XThe following symbolic costs are
Xrecognized:
X.PP
X.RS
X.nf
X.ta 14mR 17m
X\s-1LOCAL\s0    25    (local-area network connection)
X\s-1DEDICATED\s0    95    (high speed dedicated link)
X\s-1DIRECT\s0    200    (toll-free call)
X\s-1DEMAND\s0    300    (long-distance call)
X\s-1HOURLY\s0    500    (hourly poll)
X\s-1EVENING\s0    1800    (time restricted call)
X\s-1DAILY\s0    5000    (daily poll, also called \s-1POLLED\s0)
X\s-1WEEKLY\s0    30000    (irregular poll)
X.fi
X.RE
X.PP
XIn addition,
X.SM DEAD
Xis a very large number (effectively infinite),
X.SM HIGH
Xand
X.SM LOW
Xare \-5 and +5 respectively,
Xfor baud-rate or quality bonuses/penalties,
Xand
X.SM FAST
Xis \-80, for adjusting costs of links that use high-speed (9.6 Kbaud or more) modems.
XThese symbolic costs represent an imperfect measure of bandwidth,
Xmonetary cost, and frequency of connections.
XFor most mail traffic, it is important to minimize the number
Xof hosts in a route,
Xthus,
X.IR e.g. ,
X.SM HOURLY
X\&* 24
Xis much larger than
X.SM DAILY.
XIf no cost is given,
Xa default of 4000 is used.
X.PP
XFor the most part, arithmetic expressions that mix symbolic constants
Xother than
X.SM HIGH,
X.SM LOW,
Xand
X.SM FAST
Xmake no sense.
X.IR E.g. ,
Xif a host calls a local neighbor whenever there is work,
Xand additionally polls every evening,
Xthe cost is
X.SM DIRECT,
X.B not
X.SM DIRECT+EVENING.
X.PP
XSome examples:
X.PP
X.RS
X.nf
X.ta 10m 15m
Xdown    princeton!(\s-1DEDICATED\s0), tilt,
X    %thrash(\s-1LOCAL\s0)
Xprinceton    topaz!(\s-1DEMAND\s0+\s-1LOW\s0)
Xtopaz    @rutgers(\s-1LOCAL\s0+1)
X.fi
X.RE
X.PP
XIf a link is encountered more than once,
Xthe least-cost occurrence dictates the cost and network character.
XLinks are treated as bidirectional but asymmetric:
Xfor each link declared in the input, a
X.SM DEAD
Xreverse link is assumed.
X.PP
XIf the ``to'' host in a link is surrounded by angle brackets,
Xthe link is considered
X.IR terminal ,
Xand
Xfurther links beyond this one are heavily penalized.
X.IR E.g. ,
Xwith input
X.PP
X.RS
X.nf
X.ta 10m 15m
Xseismo    <research>(10), research(100), ihnp4(10)
Xresearch    allegra(10)
Xihnp4    allegra(50)
X.fi
X.RE
X.PP
Xthe path from seismo to research is direct, but the path from seismo
Xto allegra
Xuses ihnp4 as a relay, not research.
X.PP
XThe set of names by which a host is known to its neighbors is
Xcalled its
X.IR aliases .
XAliases are declared as follows:
X.PP
X.RS
Xname = alias, alias ...
X.RE
X.PP
XThe name used in the route to or through aliased hosts
Xis the name by which the host is known
Xto its predecessor in the route.
X.PP
XFully connected networks, such as the
X.SM ARPANET
Xor a local-area network,
Xare declared as follows:
X.PP
X.RS
Xnet = {host, host, ...}
X.RE
X.PP
XThe host-list may be preceded or followed by a routing
Xcharacter (`!' default), and may be followed by a cost (default 4000).
XThe network name is optional; if not given,
X.I pathalias
Xmakes one up.
X.PP
X.RS
X.nf
Xetherhosts = {rahway, milan, joliet}!(\s-1LOCAL\s0)
Xringhosts = @{gimli, alida, almo}(\s-1DEDICATED\s0)
X= {etherhosts, ringhosts}(0)
X.fi
X.RE
X.PP
XThe routing character used in a route to a network member is the one
Xencountered when ``entering'' the network.
XSee also the sections on
X.I gateways
Xand
X.I domains .
X.PP
XConnection data may be given while hiding host names
Xby declaring
X.PP
X.RS
Xprivate {host, host, ...}
X.RE
X.PP
X.I Pathalias
Xwill not generate routes for private hosts, but may produce routes
Xthrough them.
XThe scope of a private declaration extends from the declaration to the end of
Xthe input file in which it appears, or to a private declaration with an empty
Xhost list, whichever comes first.
XThe latter scope rule offers a way to retain the
Xsemantics of private declarations when
Xreading from the standard input.
X.PP
XDead hosts, links, or networks may be presented in the input stream by declaring
X.PP
X.RS
Xdead {arg, ...}
X.RE
X.PP
Xwhere
X.I arg
Xhas the same form as the argument to the
X.B \-d
Xoption.
X.PP
XTo force a specific cost for a link, delete all prior declarations with
X.PP
X.RS
Xdelete {host-1!host-2}
X.RE
X.PP
Xand declare the link as desired.
XTo delete a host and all its links, use
X.PP
X.RS
Xdelete {host}
X.RE
X.PP
XError diagnostics refer to the file in which the error was found.
XTo alter the file name, use
X.PP
X.RS
Xfile {filename}
X.RE
X.PP
XFine-tuning is possible by adjusting the weights
Xof all links from a given host, as in
X.PP
X.RS
Xadjust {host-1, host-2(LOW), host-3(\-1)}
X.RE
X.PP
XIf no cost is given a default of 4000 is used.
X.PP
XInput from compressed (and uncompressed) files can be
Xpiped into
X.I pathalias
Xwith the following script.
X.PP
X.RS
X.nf
Xfor i in $*; do
X    case $i in
X    *.Z)    echo "file {`expr $i : '\(.*\).Z'`}
X        zcat $i ;;
X    *)    echo "file {$i}"
X        cat $i ;;
X    esac
X    echo "private {}"
Xdone
X.fi
X.RE
X.PP
X.SS Output Format
XA list of host-route pairs is written to the standard output,
Xwhere route is a string appropriate for use with
X.IR printf (3),
X.IR e.g. ,
X.PP
X.RS
X.nf
X.ta 10m 20m
Xrutgers    princeton!topaz!%s@rutgers
X.fi
X.RE
X.PP
XThe ``%s'' in the route string should be replaced by the
Xuser name at the destination host.
X(This task is normally performed by a mailer.)
X.PP
XExcept for
X.IR domains ,
Xthe name of a network is never used in
Xroutes.
XThus, in the earlier example, the path from down to
Xup would be ``up!%s,'' not ``princeton-ethernet!up!%s.''
X.SS Gateways
XA network is represented by
Xa pseudo-host and a set of network members.
XLinks from the members to the network have the weight given in
Xthe input, while the cost from the network to the members is zero.
XIf a network is declared dead,
Xthe member-to-network links are marked dead,
Xwhich effectively prohibits access to the network
Xfrom its members.
X.PP
XHowever, if the input also shows an explicit link from any host to the network,
Xthen that host can be used as a gateway.
X(In particular, the gateway need not be a network member.)
X.PP
X.IR E.g. ,
Xif
X.SM CSNET
Xis declared dead
Xand the input contains
X.PP
X.RS
X.nf
X.ta 10m 20m
X\s-1CSNET\s0 = {...}
Xcsnet-relay    \s-1CSNET\s0
X.fi
X.RE
X.PP
Xthen routes to
X.SM CSNET
Xhosts will use csnet-relay as a gateway.
X.SS Domains
XA network whose name begins with `.' is called
Xa domain.
XDomains are presumed to require gateways,
X.IR i.e. ,
Xthey are \s-1DEAD\s0.
XThe route given by a path through a domain is similar to
Xthat for a network, but here
Xthe domain name is tacked onto the end of the next host.
XSubdomains are permitted.
X.PP
X.IR E.g. ,
X.PP
X.RS
X.nf
X.ta 1i
X.ta 10m 20m 30m
Xharvard    .\s-1EDU\s0    # harvard is gateway to .EDU domain
X\&.\s-1EDU\s0    = {.\s-1BERKELEY\s0, .\s-1UMICH\s0}
X\&.\s-1BERKELEY\s0    = {ernie}
X.fi
X.RE
X.PP
Xyields
X.PP
X.RS
X.nf
X.ta 10m 20m
Xernie    ...!harvard!ernie.\s-1BERKELEY\s0.\s-1EDU\s0!%s
X.fi
X.RE
X.PP
XOutput is given for the nearest gateway
Xto a domain,
X.IR e.g. ,
Xthe example above gives
X.PP
X.RS
X.nf
X.ta 10m 25m
X\&.\s-1EDU\s0    ...!harvard!%s
X.fi
X.RE
X.PP
XOutput is given for a subdomain if it has a different
Xroute than its parent domain, or if all its ancestor domains are private.
X.PP
XIf the
X.B \-D
Xoption is given on the command line,
X.I pathalias
Xtreats a link from a domain to a host member of that domain as terminal.
XThis property extends to host members of subdomains,
X.IR etc ,
Xand discourages
Xroutes that use any domain member as a relay.
X.SS Databases
X.I Makedb
Xbuilds a
X.IR dbm (3)
Xdatabase from the standard input or from the named
X.IR files .
XInput is expected to be sequence of
X.SM ASCII
Xrecords,
Xeach consisting of a key field and a data field separated by a single tab.
XIf the tab is missing, the data field is assumed to be empty.
X.SH FILES ET AL.
X.ta \w'/usr/local/lib/palias.{dir,pag}     'u
X/usr/local/lib/palias.{dir,pag}    default dbm output
X.br
Xnewsgroup comp.mail.maps    likely location of some input files
X.br
X.IR getopt (3),
Xavailable from comp.sources.unix archives (if not in the C library).
X.SH BUGS
XThe
X.B \-i
Xoption should be the default.
X.PP
XThe order of arguments is significant.
XIn particular,
X.B \-i
Xand
X.B \-t
Xshould appear early.
X.PP
X.I Pathalias
Xcan generate hybrid (\fIi.e.\fP ambiguous) routes, which are
Xabhorrent and most certainly should not be given as examples
Xin the manual entry.
XExperienced mappers largely shun `@' when preparing input; this
Xis historical, but also reflects \s-1UUCP\s0's
Xfacile syntax for source routes.
X.PP
XMultiple `@'s in routes are loathsome, so
X.I pathalias
Xresorts to the ``magic %'' rule when necessary.
XThis convention is not documented anywhere, including here.
X.PP
XThe
X.B \-D
Xoption elides insignificant routes to domain members.
XThis is benign, perhaps even beneficial, but confusing, since the
Xbehavior is undocumented and somewhat unpredictable.
X.SH SEE ALSO
XP. Honeyman and S.M. Bellovin, ``\s-1PATHALIAS\s0 \fIor\fP The Care and Feeding
Xof Relative Addresses,''
Xin \fIProc. Summer \s-1USENIX\s0 Conf.\fP, Atlanta, 1986.
END_OF_FILE
  if test 12597 -ne `wc -c <'pathalias.8'`; then
    echo shar: \"'pathalias.8'\" unpacked with wrong size!
  fi
  # end of 'pathalias.8'
fi
echo shar: End of archive 1 \(of 3\).
cp /dev/null ark1isdone
MISSING=""
for I in 1 2 3 ; do
    if test ! -f ark${I}isdone ; then
    MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have unpacked all 3 archives.
    rm -f ark[1-9]isdone
else
    echo You still must unpack the following archives:
    echo "        " ${MISSING}
fi
exit 0
exit 0 # Just in case...